package offer.day36;

public class No68First_GetLowestCommonAncestorBinaryTree {
    /*
     * 面试题68：最低公共祖先
     * 给出树中的两个节点，求这两个节点的最低公共祖先
     * 题目一：树是二叉搜索树
     *
     *
     * 思路：时间复杂度O(logn)     空间复杂度O(1)
     * 从树的根节点开始遍历，若根节点的值大于其中一个节点，小于另外一个节点，则根节点就是最低公共节点。
     * 若根结点的值小于两个节点的值，则递归求其右子树
     * 若根节点的值大于两个节点的值，则递归求其左子树
     * 若根节点的值等于其中的某一个节点，那么说明这两个节点在一条路径上，所以最低公共祖先则是根节点的父节点
     *
     * */
    public static void main(String[] args) {
        No68First_GetLowestCommonAncestorBinaryTree p =  new No68First_GetLowestCommonAncestorBinaryTree();
        BinaryTreeNode root1 = new BinaryTreeNode(5);
        BinaryTreeNode one = new BinaryTreeNode(3);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(2);
        BinaryTreeNode four = new BinaryTreeNode(4);
        BinaryTreeNode five = new BinaryTreeNode(6);
        BinaryTreeNode six = new BinaryTreeNode(8);
        BinaryTreeNode seven = new BinaryTreeNode(1);

        root1.left = one;
        root1.right = two;
        one.left = three;
        one.right = four;
        two.left = five;
        two.right = six;
        three.left = seven;
        three.right = null;
        four.left = null;
        four.right = null;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;
        seven.right = null;
        seven.left = null;
        System.out.println("两个节点的最低公共祖先："+p.GetLowestCommonAncestor(root1,root1,seven,four).val);


    }

    private BinaryTreeNode GetLowestCommonAncestor(BinaryTreeNode root, BinaryTreeNode root1, BinaryTreeNode node1, BinaryTreeNode node2) {
        if(root1==null||node1==null||node2==null) return null;
        if((root1.val-node1.val)*(root1.val-node2.val)<0){
            return root1;
        }else if((root1.val-node1.val)*(root1.val-node2.val)>0){
            BinaryTreeNode newRoot=((root1.val>node1.val)&&(root1.val>node2.val))?root1.left:root1.right;
            return GetLowestCommonAncestor(root1,newRoot,node1,node2);
        }else{
            return root;
        }
    }
}
